package sword.chapter7Queue;

import java.util.LinkedList;

/**
 * 二叉树最底层最左边的值
 *
 * 广度优先搜索
 *
 * @author K
 * @date 2021/12/6 11:40
 */
public class S45FindBottomLeftValue {
    public static int s45(TreeNode root) {
        LinkedList<TreeNode> curQueue = new LinkedList<>();
        LinkedList<TreeNode> nextQueue = new LinkedList<>();
        curQueue.offer(root);
        int result = root.val;
        while (!curQueue.isEmpty()) {
            TreeNode node = curQueue.poll();
            if (node.left != null) {
                nextQueue.offer(node.left);
            }
            if (node.right != null) {
                nextQueue.offer(node.right);
            }
            if (curQueue.isEmpty()) {
                curQueue = nextQueue;
                nextQueue = new LinkedList<>();
                if (!curQueue.isEmpty()) {
                    result = curQueue.peek().val;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        int result = s45(root);
        System.out.println();
    }
}
